/*
 * @lc app=leetcode.cn id=474 lang=golang
 *
 * [474] 一和零
 */

// @lc code=start

// dp[i][j] 表示以 i 个 0 j 个 1
func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i, _ := range dp {
		dp[i] = make([]int, n+1)
	}
	for _, v := range strs {
		count0, count1 := count(v)
		for i := m; i >= count0; i-- {
			for j := n; j >= count1; j-- {
				dp[i][j] = max(dp[i][j], dp[i-count0][j-count1]+1)
			}
		}
	}
	return dp[m][n]
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
func count(s string) (int, int) {
	count0 := len(s)
	count1 := 0
	for _, v := range s {
		if v == '1' {
			count0--
			count1++
		}
	}
	return count0, count1
}

// @lc code=end
